#include <memory.h>

#include <assert.h>

#include "uints_math.h"


void UInts_Fill(uint32_t *a, size_t size, uint32_t v) {
	for (size_t i=0; i<size; ++i) {
		a[i] = v;
	}
}

bool UInts_IsFilled(const uint32_t *a, size_t size, uint32_t v) {
	for (size_t i=0; i<size; ++i) {
		if (a[i] != v) return false;
	}
	return true;
}
 
void UInts_Copy(const uint32_t *a, size_t size, uint32_t *b) {
	for (size_t i=0; i<size; ++i) {
		b[i] = a[i];
	}
}

bool UInts_Assign(uint32_t *a, size_t asize, const uint32_t *b, size_t bsize) {

	if (asize >= bsize) {
		UInts_Fill(a, asize-bsize, 0);
		UInts_Copy(b, bsize, a+asize-bsize);
		return true;
	} else {
		UInts_Copy(b+bsize-asize, asize, a);
		return UInts_IsFilled(b, bsize-asize, 0);
	}
}

bool UInts_AssignBytes(uint32_t *a, size_t asize, const uint8_t *b, size_t bsize) {
	size_t bbsize = (bsize+3) / 4;
	uint32_t bb[bbsize];

	if (bbsize > 0) {
		size_t offset = bsize % 4;
		if (offset == 0) offset = 4;

		bb[0] = 0;
		for (size_t i=0; i<offset; ++i) {
			bb[0] = (bb[0] << 8) + b[i];
		}

		for (size_t i=1; i<bbsize; ++i) {
			size_t bi = offset + (i-1)*4;
			bb[i] = (b[bi] << 24) + (b[bi+1]<<16) + (b[bi+2]<<8) + b[bi+3];
		}
	}
	return UInts_Assign(a, asize, bb, bbsize);
}

bool UInts_AssignUInt(uint32_t *a, size_t asize, uint32_t b) {
	return UInts_Assign(a, asize, &b, 1);
}

bool UInts_ToBytes(const uint32_t *a, size_t asize, uint8_t *b, size_t bsize) {
	uint8_t bb[asize*4];

	for (size_t i=0; i<asize; ++i) {
		bb[i*4] = a[i] >> 24;
		bb[i*4+1] = a[i] >> 16;
		bb[i*4+2] = a[i] >> 8;
		bb[i*4+3] = a[i] ;
	}

	if (bsize >= asize*4) {
		memcpy(b+bsize-asize*4, bb, asize*4);
		memset(b, 0, bsize-asize*4);
		return true;
	} else {
		bool r = true;
		for (size_t i=0; i<asize*4-bsize; ++i) {
			if (bb[i] != 0) {
				r = false;
				break;
			}
		}
		memcpy(b, bb+asize*4-bsize, bsize);
		return r;
	}
}

int UInts_Compare(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize) {
	if (asize > bsize) {
		if (UInts_IsFilled(a, asize-bsize, 0)) {
			for (size_t i=0; i<bsize; ++i) {
				if (a[asize-bsize+i] > b[i]) 	  return 1;
				else if (a[asize-bsize+i] < b[i]) return -1;
				else ;
			}
		} else {
			return 1;
		}
	} else {
		if (UInts_IsFilled(b, bsize-asize, 0)) {
			for (size_t i=0; i<asize; ++i) {
				if (b[bsize-asize+i] > a[i]) 	  return -1;
				else if (b[bsize-asize+i] < a[i]) return 1;
				else ;
			}
		} else {
			return -1;
		}
	}
	return 0;
}


static size_t UInts_First(const uint32_t *a, size_t size, bool torf, uint32_t v, size_t start) {
	for (size_t i=start; i<size; ++i) {
		if (torf && a[i] == v || !torf && a[i] != v) return i;
	}
	return size;
}



bool UInts_LeftShift(const uint32_t *a, size_t asize, size_t bits, uint32_t *b, size_t bsize) {
	size_t bit32 = bits / 32;
	size_t subbits = bits % 32;
	
	uint32_t t[asize+1];

	t[0] = 0;
	if (subbits != 0) {
		for (size_t i=0; i<asize; ++i) {
			t[i] = t[i] + (a[i] >> (32-subbits));
			t[i+1] = (a[i] << subbits);
		}
	} else {
		UInts_Copy(a, asize, t+1);
	}
	
	UInts_AssignUInt(b, bsize, 0);
	return UInts_Assign(b, bsize-bit32, t, asize+1);
}

bool UInts_Add(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize, 
			   uint32_t* c, size_t csize) {
	assert(a != NULL && b != NULL && c != NULL);

	size_t rsize = (asize >= bsize ? asize : bsize) + 1;
	uint32_t r[rsize];

	UInts_Assign(r, rsize, a, asize);

	uint64_t t = 0;
	for (size_t i=0; i<bsize; ++i) {
		t = (uint64_t)r[rsize-1-i] + b[bsize-1-i] + (t>>32);
		r[rsize-1-i] = t & 0xFFFFFFFF;
	}

	for (size_t i=bsize; i<rsize && t!=0; ++i) {
		t = (uint64_t)r[rsize-1-i] + (t>>32);
		r[rsize-1-i] = t & 0xFFFFFFFF;
	}

	return UInts_Assign(c, csize, r, rsize);
}


bool UInts_Sub(const uint32_t *a, size_t asize, const uint32_t* b, size_t bsize, 
			   uint32_t* c, size_t csize) {

	size_t rsize = (asize >= bsize ? asize : bsize) + 1;
	uint32_t r[rsize];

	UInts_Assign(r, rsize, a, asize);
	
	uint64_t t = 0x100000000LL;
	for (size_t i=0; i<bsize; ++i) {
		t = 0x100000000LL + r[rsize-1-i] - b[bsize-1-i] - ((t>>32) == 0 ? 1 : 0);
		r[rsize-1-i] = t & 0xFFFFFFFF;
	}

	for (size_t i=bsize; i<rsize && (t>>32)==0; ++i) {
		t = 0x100000000 + r[rsize-1-i] - ((t>>32) == 0 ? 1 : 0);
		r[rsize-1-i] = t & 0xFFFFFFFF;
	}

	if ((t>>32) == 0) {
		if (csize >= rsize) {
			UInts_Fill(c, csize-rsize, 0xFFFFFFFF);
			UInts_Copy(r, rsize, c+csize-rsize);
		} else {
			UInts_Copy(r+rsize-csize, csize, c);
		}
		return false;
	} else {
		return UInts_Assign(c, csize, r, rsize);
	}
}





bool UInts_Mul(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize, uint32_t *c, size_t csize) {
	assert(a != NULL && b != NULL && c != NULL);
	assert(asize + bsize <= csize);

	size_t rsize = asize + bsize;
	uint32_t r[rsize];
	UInts_Fill(r, rsize, 0);
	
	for (size_t ai=0; ai<asize; ++ai) {
		for (size_t bi=0; bi<bsize; ++bi) {
			uint64_t t = r[rsize-1-ai-bi] + (uint64_t)a[asize-1-ai] * b[bsize-1-bi];
			r[rsize-1-ai-bi] = t & 0xFFFFFFFF;
			t >>= 32;
	
			for (size_t i=ai+bi+1; t!=0 && i<rsize; ++i) {
				t = (uint64_t)r[rsize-1-i] + t;
				r[rsize-1-i] = t & 0xFFFFFFFF;
				t >>= 32;
			}
		}
	}

	return UInts_Assign(c, csize, r, rsize);
}



void UInts_Div(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize, 
			uint32_t *q, size_t qsize, uint32_t *r, size_t rsize) {
	
	assert(a != NULL && b != NULL);

	uint32_t awork[asize];
	uint32_t qwork[asize];
	UInts_Copy(a, asize, awork);
	UInts_Fill(qwork, asize, 0);

	size_t aindex = 0;
	size_t bindex = UInts_First(b, bsize, false, 0, 0);
	while (UInts_Compare(awork, asize, b, bsize) >= 0) {
		aindex = UInts_First(awork, asize, false, 0, aindex);
		size_t qindex = asize - 1 - (asize-1-aindex-(bsize-1-bindex)); 
		uint64_t ah = awork[aindex];
		if (UInts_Compare(awork+aindex, bsize-bindex, b+bindex, bsize-bindex) < 0) {
			qindex += 1;
			ah = (ah << 32) + awork[aindex+1];
		}

		uint32_t top = ah / b[bindex];
		uint32_t bottom = ah / (b[bindex] + 1);
		if (bottom == 0) bottom = 1;
		uint32_t mid = ((uint64_t)top + bottom + 1) / 2;

		while (1) {
			uint32_t bwork[bsize+1];
			UInts_Assign(bwork, bsize+1, b, bsize);
			UInts_Mul(b, bsize, &mid, 1, bwork, bsize+1);

			if (UInts_Compare(awork, qindex+1, bwork, bsize+1) >= 0) {
				UInts_Sub(awork, qindex+1, bwork, bsize+1, awork, qindex+1);
				qwork[qindex] += mid;
				break;
			} else {
				mid = ((uint64_t)mid + mid + bottom) / 3;
			}
		}
	}

	 (r == NULL || UInts_Assign(r, rsize, awork, asize)) &&
		   (q == NULL || UInts_Assign(q, qsize, qwork, asize));

}


void UInts_Not(const uint32_t *a, uint32_t *b, size_t size) {
	for (size_t i=0; i<size; ++i) {
		b[i] = ~a[i];
	}
}

void UInts_And(const uint32_t *a, const uint32_t *b, uint32_t *c, size_t size) {
	for (size_t i=0; i<size; ++i) {
		c[i] = a[i] & b[i];
	}
}

void UInts_Or(const uint32_t *a, const uint32_t *b, uint32_t *c, size_t size) {
	for (size_t i=0; i<size; ++i) {
		c[i] = a[i] | b[i];
	}
}

void UInts_Xor(const uint32_t *a, const uint32_t *b, uint32_t *c, size_t size) {
	for (size_t i=0; i<size; ++i) {
		c[i] = a[i] ^ b[i];
	}
}

bool UInts_BitAdd(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize, uint32_t *c, size_t csize) {
	size_t tsize = asize >= bsize ? asize : bsize;
	uint32_t t[tsize];

	UInts_Assign(t, tsize, a, asize);

	UInts_Xor(t+tsize-bsize, b, t+tsize-bsize, bsize);
	UInts_Not(t, t, tsize-bsize);

	return UInts_Assign(c, csize, t, tsize);
}

bool UInts_BitSub(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize, uint32_t *c, size_t csize) {
	return UInts_BitAdd(a, asize, b, bsize, c, csize);
}


bool UInts_BitMul(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize, uint32_t *c, size_t csize) {
	uint32_t t[asize+bsize];
	UInts_AssignUInt(t, asize+bsize, 0);

	for (size_t i=0; i<bsize; ++i) {
		
		for (size_t j=0; j<sizeof(uint32_t)*8; ++j) {
			if ((b[bsize-1-i] & (1<<j)) != 0) {
				uint32_t asub[asize+1];
				UInts_LeftShift(a, asize, j, asub, asize+1);
				UInts_BitAdd(t+bsize-1-i, asize+1, asub, asize+1, t+bsize-1-i, asize+1);
			}
		}
	}

	return UInts_Assign(c, csize, t, asize+bsize);
}

bool UInts_GetBit(const uint32_t *a, size_t asize, size_t index) {
	size_t mainIndex = index / 32;
	size_t subIndex = index % 32;
	
	return mainIndex < asize ? (a[asize-1-mainIndex] & (1<<subIndex)) != 0 : 0;
}

bool UInts_SetBit(uint32_t *a, size_t asize, size_t index, bool v) {
	size_t mainIndex = index / 32;
	size_t subIndex = index % 32;

	a[asize-1-mainIndex] |= (1<<subIndex);
	return mainIndex < asize;
}

bool UInts_BitDiv(const uint32_t *a, size_t asize, const uint32_t *b, size_t bsize, uint32_t *q, size_t qsize, uint32_t *r, size_t rsize) {
	bool retVal = true;

	uint32_t rwork[asize];
	uint32_t qwork[asize];

	UInts_Assign(rwork, asize, a, asize);
	UInts_AssignUInt(qwork, asize, 0);
	
	size_t bhbit = UInts_HighestBit(b, bsize);
	size_t rhbit = UInts_HighestBit(rwork, asize);

	for (size_t i=bhbit; i<=rhbit; ++i) {
		if (UInts_GetBit(rwork, asize, rhbit-(i-bhbit))) {
			uint32_t bwork[asize];
			UInts_LeftShift(b, bsize, rhbit-i, bwork, asize);
			UInts_BitSub(rwork, asize, bwork, asize, rwork, asize);
			UInts_SetBit(qwork, asize, rhbit-i, true);
		}
	}
	
	if (r != NULL ) {
		retVal = UInts_Assign(r, rsize, rwork, asize) && retVal;
	} else {
		retVal = UInts_IsZero(rwork, asize) && retVal;
	}

	if (q != NULL) {
		retVal = UInts_Assign(q, qsize, qwork, asize) && retVal;
	} else {
		retVal = UInts_IsZero(qwork, asize) && retVal;
	}
	return retVal;
}

size_t UInts_HighestDigit(const uint32_t *a, size_t asize) {
	for (size_t i=0; i<asize; ++i) {
		if (a[i] != 0) return asize - 1 - i;
	}

	return UInts_DigitSize(a, asize);
}

size_t UInts_HighestBit(const uint32_t *a, size_t asize) {
	size_t index = UInts_HighestDigit(a, asize);

	if (index < UInts_DigitSize(a, asize)) {
		uint32_t d = UInts_GetDigit(a, asize, index);

		for (size_t i=8*sizeof(uint32_t); i>0; --i) {
			if ((d & (1<<(i-1))) != 0) {
				return index*8*sizeof(uint32_t) + i-1;
			}
		}
		assert(!"不应该进入这里");
	}

	return UInts_BitSize(a, asize);
}
